#![allow(dead_code, mutable_transmutes, non_camel_case_types, non_snake_case, non_upper_case_globals, unused_assignments, unused_mut)]
use std::mem;
use crate::alloc_testing::*;
extern "C" {
            }
pub type size_t = libc::c_ulong;
#[derive(Copy, Clone)]
#[repr(C)]
pub struct _Trie {
    pub root_node: *mut TrieNode,
}
pub type TrieNode = _TrieNode;
#[derive(Copy, Clone)]
#[repr(C)]
pub struct _TrieNode {
    pub data: TrieValue,
    pub use_count: libc::c_uint,
    pub next: [*mut TrieNode; 256],
}
pub type TrieValue = *mut libc::c_void;
pub type Trie = _Trie;
#[no_mangle]
pub extern "C" fn trie_new() -> *mut Trie {
    let new_trie: *mut Trie = unsafe {
        alloc_test_malloc(std::mem::size_of::<Trie>() as libc::c_ulong) as *mut Trie
    };

    if new_trie.is_null() {
        return std::ptr::null_mut();
    }

    let mut boxed_trie = unsafe { Box::from_raw(new_trie) };
    boxed_trie.root_node = std::ptr::null_mut();
    let new_trie = Box::into_raw(boxed_trie);

    new_trie
}
extern "C" fn trie_free_list_push(
    mut list: *mut *mut TrieNode,
    mut node: *mut TrieNode,
) {
    let mut boxed_node = unsafe { Box::from_raw(node) };
    let mut boxed_list = unsafe { Box::from_raw(list) };
    boxed_node.data = *boxed_list as TrieValue;
    *boxed_list = node;
    let list = Box::into_raw(boxed_list);
    let node = Box::into_raw(boxed_node);
}
extern "C" fn trie_free_list_pop(mut list: *mut *mut TrieNode) -> *mut TrieNode {
    let mut result: *mut TrieNode = std::ptr::null_mut();

    let mut boxed_list = unsafe { Box::from_raw(list) };
    result = *boxed_list;
    *boxed_list = unsafe { (*result).data as *mut TrieNode };
    list = Box::into_raw(boxed_list);

    result
}
#[no_mangle]
pub extern "C" fn trie_free(mut trie: *mut Trie) {
    let mut free_list: *mut TrieNode = std::ptr::null_mut();
    let mut node: *mut TrieNode = std::ptr::null_mut();
    let mut i: libc::c_int = 0;

    if !trie.is_null() {
        let boxed_trie = unsafe { Box::from_raw(trie) };
        if !boxed_trie.root_node.is_null() {
            trie_free_list_push(&mut free_list, boxed_trie.root_node);
        }
        trie = Box::into_raw(boxed_trie);
    }

    while !free_list.is_null() {
        node = trie_free_list_pop(&mut free_list);
        i = 0;
        while i < 256 {
            if !node.is_null() && !unsafe { (*node).next[i as usize].is_null() } {
                trie_free_list_push(&mut free_list, unsafe { (*node).next[i as usize] });
            }
            i += 1;
        }
        if !node.is_null() {
            alloc_test_free(node as *mut libc::c_void);
        }
    }

    if !trie.is_null() {
        alloc_test_free(trie as *mut libc::c_void);
    }
}
extern "C" fn trie_find_end(
    mut trie: *mut Trie,
    mut key: *mut libc::c_char,
) -> *mut TrieNode {
    let mut node: *mut TrieNode = std::ptr::null_mut();
    let mut p: *mut libc::c_char = std::ptr::null_mut();

    let boxed_trie = unsafe { Box::from_raw(trie) };
    node = boxed_trie.root_node;
    p = key;

    while unsafe { *p } != b'\0' as libc::c_char {
        if node.is_null() {
            let trie = Box::into_raw(boxed_trie);
            return std::ptr::null_mut();
        }
        
        node = unsafe { (*node).next[*p as libc::c_uchar as usize] };
        p = unsafe { p.offset(1) };
    }

    let trie = Box::into_raw(boxed_trie);
    node
}
extern "C" fn trie_find_end_binary(
    mut trie: *mut Trie,
    mut key: *mut libc::c_uchar,
    mut key_length: libc::c_int,
) -> *mut TrieNode {
    let mut node: *mut TrieNode = std::ptr::null_mut();
    let mut j: libc::c_int = 0;
    let mut c: libc::c_int = 0;

    let boxed_trie = unsafe { Box::from_raw(trie) };
    node = boxed_trie.root_node;
    let trie = Box::into_raw(boxed_trie);

    while j < key_length {
        if node.is_null() {
            return std::ptr::null_mut();
        }

        c = unsafe { *key.offset(j as isize) as libc::c_int };

        node = unsafe { (*node).next[c as usize] };

        j += 1;
    }

    node
}
extern "C" fn trie_insert_rollback(
    mut trie: *mut Trie,
    mut key: *mut libc::c_uchar,
) {
    let mut node: *mut TrieNode = std::ptr::null_mut();
    let mut prev_ptr: *mut *mut TrieNode = std::ptr::null_mut();
    let mut next_node: *mut TrieNode = std::ptr::null_mut();
    let mut next_prev_ptr: *mut *mut TrieNode = std::ptr::null_mut();
    let mut p: *mut libc::c_uchar = std::ptr::null_mut();

    let mut boxed_trie = unsafe { Box::from_raw(trie) };
    node = boxed_trie.root_node;
    prev_ptr = &mut boxed_trie.root_node;
    p = key;

    while !node.is_null() {
        let mut boxed_node = unsafe { Box::from_raw(node) };
        next_prev_ptr = unsafe {
            &mut *((*boxed_node).next).as_mut_ptr().offset(*p as isize)
                as *mut *mut TrieNode
        };
        next_node = unsafe { *next_prev_ptr };
        p = unsafe { p.offset(1) };
        boxed_node.use_count = boxed_node.use_count.wrapping_sub(1);

        if boxed_node.use_count == 0 {
            alloc_test_free(node as *mut libc::c_void);
            if !prev_ptr.is_null() {
                unsafe { *prev_ptr = std::ptr::null_mut(); }
            }
            next_prev_ptr = std::ptr::null_mut();
        }

        node = next_node;
        prev_ptr = next_prev_ptr;
        let node = Box::into_raw(boxed_node);
    }

    let trie = Box::into_raw(boxed_trie);
}
#[no_mangle]
pub extern "C" fn trie_insert(
    mut trie: *mut Trie,
    mut key: *mut libc::c_char,
    mut value: TrieValue,
) -> libc::c_int {
    let mut rover: *mut *mut TrieNode = std::ptr::null_mut();
    let mut node: *mut TrieNode = std::ptr::null_mut();
    let mut p: *mut libc::c_char = std::ptr::null_mut();
    let mut c: libc::c_int = 0;

    if value.is_null() {
        return 0;
    }

    node = trie_find_end(trie, key);

    if !node.is_null() && !unsafe { (*node).data.is_null() } {
        unsafe {
            (*node).data = value;
        }
        return 1;
    }

    let mut boxed_trie = unsafe { Box::from_raw(trie) };
    rover = &mut boxed_trie.root_node;
    p = key;

    loop {
        node = unsafe { *rover };

        if node.is_null() {
            node = unsafe {
                alloc_test_calloc(
                    1,
                    std::mem::size_of::<TrieNode>().try_into().unwrap(),
                ) as *mut TrieNode
            };

            if node.is_null() {
                unsafe {
                    trie_insert_rollback(trie, key as *mut libc::c_uchar);
                }
                return 0;
            }

            unsafe {
                (*node).data = std::ptr::null_mut();
                *rover = node;
            }
        }

        unsafe {
            (*node).use_count = (*node).use_count.wrapping_add(1);
        }

        c = unsafe { *p as libc::c_uchar as libc::c_int };

        if c == '\0' as i32 {
            unsafe {
                (*node).data = value;
            }
            break;
        } else {
            unsafe {
                rover = &mut *((*node).next).as_mut_ptr().offset(c as isize)
                    as *mut *mut TrieNode;
            }
            p = unsafe { p.offset(1) };
        }
    }

    trie = Box::into_raw(boxed_trie);
    return 1;
}
#[no_mangle]
pub extern "C" fn trie_insert_binary(
    mut trie: *mut Trie,
    mut key: *mut libc::c_uchar,
    mut key_length: libc::c_int,
    mut value: TrieValue,
) -> libc::c_int {
    let mut rover: *mut *mut TrieNode = std::ptr::null_mut();
    let mut node: *mut TrieNode = std::ptr::null_mut();
    let mut p: libc::c_int = 0;
    let mut c: libc::c_int = 0;

    if value.is_null() {
        return 0;
    }

    node = trie_find_end_binary(trie, key, key_length);

    if !node.is_null() {
        let mut boxed_node = unsafe { Box::from_raw(node) };
        if !boxed_node.data.is_null() {
            boxed_node.data = value;
            node = Box::into_raw(boxed_node);
            return 1;
        }
        node = Box::into_raw(boxed_node);
    }

    let mut boxed_trie = unsafe { Box::from_raw(trie) };
    rover = &mut boxed_trie.root_node;
    p = 0;

    loop {
        node = unsafe { *rover };

        if node.is_null() {
            node = alloc_test_calloc(
                1,
                std::mem::size_of::<TrieNode>().try_into().unwrap(),
            ) as *mut TrieNode;

            if node.is_null() {
                trie_insert_rollback(trie, key);
                return 0;
            }

            let mut boxed_node = unsafe { Box::from_raw(node) };
            boxed_node.data = std::ptr::null_mut();
            unsafe { *rover = node; }
            node = Box::into_raw(boxed_node);
        }

        let mut boxed_node = unsafe { Box::from_raw(node) };
        boxed_node.use_count = boxed_node.use_count.wrapping_add(1);
        node = Box::into_raw(boxed_node);

        c = unsafe { *key.offset(p as isize) as libc::c_int };

        if p == key_length {
            let mut boxed_node = unsafe { Box::from_raw(node) };
            boxed_node.data = value;
            node = Box::into_raw(boxed_node);
            break;
        } else {
            rover = unsafe {
                &mut *((*node).next).as_mut_ptr().offset(c as isize) as *mut *mut TrieNode
            };
            p += 1;
        }
    }

    trie = Box::into_raw(boxed_trie);
    return 1;
}
#[no_mangle]
pub extern "C" fn trie_remove_binary(
    mut trie: *mut Trie,
    mut key: *mut libc::c_uchar,
    mut key_length: libc::c_int,
) -> libc::c_int {
    let mut node: *mut TrieNode = std::ptr::null_mut();
    let mut next: *mut TrieNode = std::ptr::null_mut();
    let mut last_next_ptr: *mut *mut TrieNode = std::ptr::null_mut();
    let mut p: libc::c_int = 0;
    let mut c: libc::c_int = 0;

    let mut boxed_trie = unsafe { Box::from_raw(trie) };
    node = trie_find_end_binary(trie, key, key_length);
    if !node.is_null() && !unsafe { (*node).data }.is_null() {
        unsafe { (*node).data = std::ptr::null_mut(); }
    } else {
        trie = Box::into_raw(boxed_trie);
        return 0;
    }

    node = boxed_trie.root_node;
    last_next_ptr = &mut boxed_trie.root_node;
    p = 0;

    loop {
        c = unsafe { *key.offset(p as isize) } as libc::c_int;
        next = unsafe { (*node).next[c as usize] };
        unsafe { (*node).use_count = (*node).use_count.wrapping_sub(1); }

        if unsafe { (*node).use_count == 0 } {
            alloc_test_free(node as *mut libc::c_void);
            if !last_next_ptr.is_null() {
                unsafe { *last_next_ptr = std::ptr::null_mut(); }
                last_next_ptr = std::ptr::null_mut();
            }
        }

        if p == key_length {
            break;
        }

        p += 1;

        if !last_next_ptr.is_null() {
            last_next_ptr = unsafe { &mut *((*node).next).as_mut_ptr().offset(c as isize) as *mut *mut TrieNode };
        }

        node = next;
    }

    trie = Box::into_raw(boxed_trie);
    return 1;
}
#[no_mangle]
pub extern "C" fn trie_remove(
    mut trie: *mut Trie,
    mut key: *mut libc::c_char,
) -> libc::c_int {
    let mut node: *mut TrieNode = std::ptr::null_mut();
    let mut next: *mut TrieNode = std::ptr::null_mut();
    let mut last_next_ptr: *mut *mut TrieNode = std::ptr::null_mut();
    let mut p: *mut libc::c_char = std::ptr::null_mut();
    let mut c: libc::c_int = 0;

    let mut boxed_trie = unsafe { Box::from_raw(trie) };
    node = trie_find_end(trie, key);
    if !node.is_null() && !unsafe { (*node).data.is_null() } {
        unsafe {
            (*node).data = std::ptr::null_mut();
        }
    } else {
        trie = Box::into_raw(boxed_trie);
        return 0;
    }
    node = boxed_trie.root_node;
    last_next_ptr = &mut boxed_trie.root_node;
    p = key;

    loop {
        unsafe {
            c = *p as libc::c_uchar as libc::c_int;
            next = (*node).next[c as usize];
            (*node).use_count = (*node).use_count.wrapping_sub(1);
            if (*node).use_count <= 0 {
                alloc_test_free(node as *mut libc::c_void);
                if !last_next_ptr.is_null() {
                    *last_next_ptr = std::ptr::null_mut();
                    last_next_ptr = std::ptr::null_mut();
                }
            }
            if c == '\0' as i32 {
                break;
            }
            p = p.offset(1);
            if !last_next_ptr.is_null() {
                last_next_ptr = &mut *((*node).next).as_mut_ptr().offset(c as isize)
                    as *mut *mut TrieNode;
            }
            node = next;
        }
    }

    trie = Box::into_raw(boxed_trie);
    return 1;
}
#[no_mangle]
pub extern "C" fn trie_lookup(
    mut trie: *mut Trie,
    mut key: *mut libc::c_char,
) -> TrieValue {
    let mut node: *mut TrieNode = std::ptr::null_mut();

    node = trie_find_end(trie, key);

    if !node.is_null() {
        let boxed_node = unsafe { Box::from_raw(node) };
        let data = boxed_node.data;
        let node = Box::into_raw(boxed_node);
        return data;
    } else {
        return std::ptr::null_mut();
    }
}
#[no_mangle]
pub extern "C" fn trie_lookup_binary(
    mut trie: *mut Trie,
    mut key: *mut libc::c_uchar,
    mut key_length: libc::c_int,
) -> TrieValue {
    let mut node: *mut TrieNode = std::ptr::null_mut();

    node = trie_find_end_binary(trie, key, key_length);

    if !node.is_null() {
        let boxed_node = unsafe { Box::from_raw(node) };
        let data = boxed_node.data;
        let node = Box::into_raw(boxed_node);
        return data;
    } else {
        return std::ptr::null_mut();
    }
}
#[no_mangle]
pub extern "C" fn trie_num_entries(mut trie: *mut Trie) -> libc::c_uint {
    if trie.is_null() {
        return 0;
    }

    let boxed_trie = unsafe { Box::from_raw(trie) };
    if boxed_trie.root_node.is_null() {
        let trie = Box::into_raw(boxed_trie);
        return 0;
    } else {
        let use_count = unsafe { (*boxed_trie.root_node).use_count };
        let trie = Box::into_raw(boxed_trie);
        return use_count;
    }
}
